package cn.jingyuan.bee.utils.math;

import cn.jingyuan.bee.utils.ArrayUtils;
import cn.jingyuan.bee.utils.NumberUtils;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 排列 A(n, m)<br>
 * 排列组合相关类 参考：http://cgs1999.iteye.com/blog/2327664
 */
public class Arrangement implements Serializable {

    private final String[] data;

    /**
     * 构造
     *
     * @param data 用于排列的数据
     */
    public Arrangement(String[] data) {
        this.data = data;
    }

    /**
     * 计算排列数，即 A(n, n) = n!
     *
     * @param n 总数
     *
     * @return 排列数
     */
    public static long count(int n) {
        return count(n, n);
    }

    /**
     * 计算排列数，即 A(n, m) = n!/(n-m)!
     *
     * @param n 总数
     * @param m 选择的个数
     *
     * @return 排列数
     */
    public static long count(int n, int m) {
        if (n == m) {
            return NumberUtils.factorial(n);
        }
        return (n > m) ? NumberUtils.factorial(n, n - m) : 0;
    }

    /**
     * 计算排列总数，即 A(n, 1) + A(n, 2) + A(n, 3)...
     *
     * @param n 总数
     *
     * @return 排列数
     */
    public static long countAll(int n) {
        long total = 0;
        for (int i = 1; i <= n; i++) {
            total += count(n, i);
        }
        return total;
    }

    /**
     * 全排列选择（列表全部参与排列）
     *
     * @return 所有排列列表
     */
    public List<String[]> select() {
        return select(this.data.length);
    }

    /**
     * 排列选择（从列表中选择 m 个排列）
     *
     * @param m 选择个数
     *
     * @return 所有排列列表
     */
    public List<String[]> select(int m) {
        final List<String[]> result = new ArrayList<>((int) count(this.data.length, m));
        select(this.data, new String[m], 0, result);
        return result;
    }

    /**
     * 排列所有组合，即 A(n, 1) + A(n, 2) + A(n, 3)...
     *
     * @return 全排列结果
     */
    public List<String[]> selectAll() {
        final List<String[]> result = new ArrayList<>((int) countAll(this.data.length));
        for (int i = 1; i <= this.data.length; i++) {
            result.addAll(select(i));
        }
        return result;
    }

    /**
     * 排列选择<br>
     * 排列方式为先从数据数组中取出一个元素，再把剩余的元素作为新的基数，依次列推，直到选择到足够的元素
     *
     * @param data 选择的基数
     * @param resultList 前面（resultIndex-1）个的排列结果
     * @param resultIndex 选择索引，从 0 开始
     * @param result 最终结果
     */
    private void select(String[] data, String[] resultList, int resultIndex, List<String[]> result) {
        // 全部选择完时，输出排列结果
        if (resultIndex >= resultList.length) {
            if (!result.contains(resultList)) {
                result.add(Arrays.copyOf(resultList, resultList.length));
            }
            return;
        }

        // 递归选择下一个
        for (int i = 0; i < data.length; i++) {
            resultList[resultIndex] = data[i];
            select(ArrayUtils.remove(data, i), resultList, resultIndex + 1, result);
        }
    }

}
